package digui;

public class _07奇数在左偶数在右 {
    public static void main(String[] args) {
        int[] a = {2,4,6,1,3,5,8,7};
        int[] change = case2(a);
        for (int i = 0 ; i < change.length;i++){
            System.out.print(change[i] + " ");
        }
    }

    //奇数在左，偶数在右（使用归并思想，开辟新数组，左右指针扫描,需要消耗一个空间O（n））
    public static int[] case1(int[] a){
        int n = a.length;
        int first = 0;
        int last = n-1;
        int[] help = new int[n];
        while (first<=last){
            for (int i = 0 ; i < n ;i++){
                if (a[i] % 2 == 0){
                    help[last] = a[i];
                    last--;
                }else {
                    help[first] = a[i];
                    first ++;
                }
            }
        }
        return help;
    }

    //不需要新开空间，使用快排思想，在原数组上左右指针移动
    public static int[] case2(int[] a){
        int n = a.length;
        int first = 0;
        int last = n-1;
        while (first< last){
            while ((a[first] % 2 == 1&& first<last)){
                first++;
            }
            while (a[last] % 2==0 && first<last){
                last --;
            }
            swap(a,first,last);
        }

        return a;
    }
    private static void swap(int[] a, int pivot, int i) {
        int temp = a[pivot];
        a[pivot] = a[i];
        a[i]= temp;
    }

}
